
#ifndef _DATASTRCT_H
#define _DATASTRCT_H

#include "simdef.h"


#define QueueElem int32_t
struct QueueRecord
{
    uint32_t capacity;
    uint32_t front;
    uint32_t rear;
    uint32_t size;
    QueueElem* array;
};
typedef struct QueueRecord* Queue;

#define ListElem int32_t
struct Node
{
    ListElem element;
    struct Node* next;
};
typedef struct Node* List;
typedef struct Node* ListPos;

#define SKIPLIST_MAXLEVEL 8
#define SKIPLIST_P 2
#define skiplistElem int32_t
#define ScoreType int32_t

//   ◄──┐
//      │    level:
// ┌────┴───┬────┬───────┐
// │backward│span│forward├────►
// │        ├────┼───────┤
// ├────────┤span│forward├────►
// │element ├────┼───────┤
// │score   │span│forward├────►
// └────────┴────┴───────┘
typedef struct ZskiplistNode {
    skiplistElem element;
    ScoreType score;
    struct ZskiplistNode *backward;
    struct SkiplistLevel {
        struct ZskiplistNode *forward;
        uint32_t span; // 这个层跨越的节点数量
    } level[];
} SlNode_t;

typedef struct Zskiplist {
    struct ZskiplistNode *head; 
    struct ZskiplistNode *tail;
    int32_t length; // 节点数量
    int32_t level; // 目前表内节点的最大层数
} SlList_t;

enum FlagSerchSl{
    EQUAL=0,
    GE,
    LE
};

typedef struct {
    SlNode_t *headNode;
    SlNode_t *tailNode;
} rangeSerchRst_t;


/*---------------queue---------------*/
int32_t isQueEmpty(Queue Q);
int32_t isQueFull(Queue Q);
Queue createQueue(uint32_t NElements);
void emptyQue(Queue Q);
void disposeQue(Queue Q);
static uint32_t succ(uint32_t value, Queue Q);
int32_t inQue(QueueElem data, Queue Q);
int32_t deQue(QueueElem* data,Queue Q);
/*---------------Linked list---------------*/
List emptyList(List L);
void deleList(List L);
int32_t isListEmpty(List L);
void deleNode(ListPos preNode);
int32_t insertNode(ListPos prenode, ListElem data);
int32_t appendNode(List L, ListElem data);
void printList(List L, void (*printMethod)(void *arg));
/*----------------- jamp list -----------------*/
SlList_t* createSlList();
SlNode_t* createSlNode(int32_t level,
                    ScoreType score,
                    skiplistElem* element);
SlNode_t* insertNodeSl(SlList_t* slList,
                ScoreType score,
                skiplistElem* element);
uint32_t slRandomLevel();
void deletNodeSl(SlList_t* slList,SlNode_t *node);
SlNode_t* serchSl(SlList_t* slList,ScoreType score,int32_t flag);
rangeSerchRst_t RangeSerchSl(SlList_t* slList,ScoreType s1,ScoreType s2);
void printRangeSerchRst(SlList_t* slList,rangeSerchRst_t* result);
int32_t rankSerchSl(SlList_t* slList,ScoreType score,int32_t flag);
void printSl(SlList_t* slList);
void freeSlList(SlList_t* slList);
void freeSlNode(SlNode_t* node);
/*---------------Algorithm---------------*/
void findMaxUint64(
    uint64_t* maxVal, uint32_t* index, // output
    uint64_t* list, uint32_t start, uint32_t end);
uint64_t myMeanUint64(uint64_t* list, uint32_t start, uint32_t end);
uint32_t myMaxUint32(uint32_t a, uint32_t b);
uint32_t myMinUint32(uint32_t a, uint32_t b);
uint32_t myAbsInt32(int32_t a);
/*----------------- rand -----------------*/
uint32_t myRand();
void mySrand(uint32_t seed);

#endif // _DATASTRCT_H
